// 72 编辑距离
// https://leetcode.cn/problems/edit-distance/
// 这题考的是动态规划，难度很大，为了成功做出此题，下面这几个视频必看
// LeetCode：718.最长重复子数组 https://www.bilibili.com/video/BV178411H7hV/?spm_id_from=333.788&vd_source=4fd973d19cb5506a7c9f2d59e8ab5165

/**

示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
 */

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    // dp数组定义，dp[i][j]为要使nums1[0,i-1]和nums2[0,j-1]完全相等的步数

    let dp = new Array(word1.length + 1)
        .fill(0)
        .map(() => new Array(word2.length + 1).fill(0));

    for (let i = 0; i <= word2.length; i++) {
        dp[0][i] = i;
    }

    for (let i = 0; i <= word1.length; i++) {
        dp[i][0] = i;
    }

    // printDP(dp, word1, word2);

    for (let i = 1; i <= word1.length; i++) {
        for (let j = 1; j <= word2.length; j++) {
            const i1 = i - 1;
            const j1 = j - 1;

            if (word1[i1] === word2[j1]) {
                dp[i][j] += dp[i1][j1]; // 如果完全相等，就不需要进行特殊操作就能相等
            } else {
                // 删除
                // dp[i1][j] 或者 dp[i][j1]都可以
                // dp[i][j] = 1 + dp[i1][j];
                // 替换
                // dp[i][j] = 1 + dp[i1][j1];
                // 插入 插入就是另一边的删除，不做操作
                // dp[i][j] = 1 + dp[i1][j1];

                dp[i][j] = Math.min(dp[i1][j], dp[i][j1], dp[i1][j1]) + 1;
            }
        }
    }

    printDP(dp, word1, word2);

    console.log(
        `[findLength] ${word1},${word2}: ${dp[word1.length][word2.length]}`
    );

    return dp[word1.length][word2.length];
};

var printDP = function (dp, word1, word2) {
    let arr = JSON.parse(JSON.stringify(dp));

    let title = [''];
    let col = [''];
    let arrWord1 = word1.split('');
    let arrWord2 = word2.split('');

    for (let i = 0; i < word2.length; i++) {
        title.push('' + arrWord2.slice(0, i + 1).join(''));
    }

    for (let i = 0; i <= word1.length; i++) {
        col.push('' + arrWord1.slice(0, i).join(''));
    }

    arr.splice(0, 0, title);

    for (let i = 0; i < arr.length; i++) {
        arr[i].splice(0, 0, col[i]);
    }

    console.table(arr);
};

minDistance('horse', 'ros');
minDistance('intention', 'execution');
minDistance('', 'a');
minDistance('a', 'ab');
